Những năm đầu tiên / Hamburg / Fiorentina

Sinh ra tại Rýmařov, Tiệp Khắc cùng gốc gác Hungary[5] – Ujfaluši có trận đá chuyên nghiệp đầu tiên trong màu áo SK Sigma Olomouc, năm anh 18 tuổi. Tháng 12 năm 2000, anh ra nước ngoài thi đấu và ký hợp đồng với câu lạc bộ Hamburger SV của Đức: anh có trận ra mắt đội vào ngày 10 tháng 12 sau khi chơi 90 phút trong trận thắng 2–1 trên sân nhà trước FC Energie Cottbus, và hoàn tất 16 trên 17 trận ra sân ở mùa giải đó, nhưng đội bóng chỉ có thể xếp ở vị trí thứ 13 và 11 ở chiến dịch tiếp theo, với lần lượt 58 và 57 bàn bị thủng lưới.

Ở mùa 2002–03 Ujfaluši giúp Hamburg cán đích ở vị trí thứ 4, nhưng đội lại thi đấu tệ hơn ở mùa giải kế tiếp (một lần nữa để thủng lưới khoảng 50 bàn ở Bundesliga). Sau đó anh ký hợp đồng với ACF Fiorentina, đội bóng mới trở lại Serie A sau khi thoát hiểm khỏi nguy cơ bị phá sản.

Atlético Madrid

Sau gần 150 trận đấu chính thức cho Viola, anh được sử dụng chủ yếu ở vị trí trung vệ bởi huấn luyện viên Cesare Prandelli, Ujfaluši đầu quân cho Atlético Madrid dưới dạng chuyển nhượng tự do,[6] giúp cho đội bóng thủ đô tái lập hạng 4 tại giải La Liga trong mùa giải anh ra mắt, qua đó giành vé đi UEFA Champions League 2009–10.

Tại mùa giải vô địch Tây Ban Nha 2009–10 Atlético chỉ kết thúc ở vị trí thứ 9 nhưng lại vô địch giải đấu cúp châu Âu mới lập là UEFA Europa League, giúp Ujfaluši góp mặt ở 8 trận đấu ở cúp châu Âu. Ngày 19 tháng 9 năm 2010, trong thời gian bù giờ của trận thua 1–2 trước FC Barcelona tại Vicente Calderón Stadium, anh đã thực hiện một pha truy cản với cầu thủ Lionel Messi và làm mắt cá chân phải của anh dính chấn thương. Hậu vệ này phải nhận tấm thẻ đỏ trực tiếp vì pha phạm lỗi ấy, qua đó bị Ủy ban kỷ luật của Liên đoàn bóng đá Tây Ban Nha treo giò hai trận kế tiếp;[7][8][9] anh chiếm một suất đá chính ở mùa giải kế tiếp – chủ yếu ở vị trí hậu vệ phỉa – giúp Colchoneros cán đích ở vị trí thứ 7 và giành vé dự Europa League.